package medium

import (
	. "GoLeetcode/common"
	"fmt"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
时间复杂度:O(N^2)
空间复杂度：O(N^2)

中序遍历整棵树的每个节点，然后将每棵子树的序列化表示存入hash中，从而判断是否有重复子树
TODO:唯一标识符解法
*/
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
	// 这里只存储value为2的子树的序列化表示(避免一颗子树重复出现多次，导致result中存储了多个重复的数据)
	hash := make(map[string]int)
	result := make([]*TreeNode, 0)
	// dfs返回的是以node节点为根节点的树的序列化表示
	var dfs func(node *TreeNode) string
	dfs = func(node *TreeNode) string {
		if node == nil {
			return "#"
		}
		s := fmt.Sprintf("%v:%v:%v", node.Val, dfs(node.Left), dfs(node.Right))
		hash[s]++
		if hash[s] == 2 {
			result = append(result, node)
		}
		return s
	}
	dfs(root)
	return result
}